class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int m = nums.size();
        vector<int>prefix(m);
        vector<int>suffix(m);
        vector<int>ret(m);
        for (int i = 0; i < m; i++)
        {
            if (i == 0)prefix[i] = 1;
            else prefix[i] = prefix[i - 1] * nums[i - 1];
        }
        for (int i = m - 1; i >= 0; i--)
        {
            if (i == m - 1)suffix[i] = 1;
            else suffix[i] = suffix[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < m; i++)
        {
            ret[i] = prefix[i] * suffix[i];
        }
        return ret;




    }
}; class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int lenth = 0;
        int maxp = 0;
        int m = s.size();
        int left = 0;
        int right = 0;
        unordered_set<char>st;
        while (right < m)
        {

            if (!st.count(s[right]))
            {
                st.insert(s[right]);
                lenth++;
                maxp = max(lenth, maxp);
            }
            else
            {
                while (st.count(s[right]))
                {
                    st.erase(s[left]);
                    left++;
                    lenth--;
                }
                st.insert(s[right]);
                lenth++;
                maxp = max(maxp, lenth);
            }

            right++;


        }
        return maxp;
    }
};/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr)return nullptr;
        ListNode* n1 = nullptr;
        ListNode* n2 = head;

        ListNode* n3 = head->next;
        while (n2)
        {

            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
                n3 = n3->next;

        }

        return n1;

    }

    bool isPalindrome(ListNode* head) {
        ListNode* newhead = new ListNode(head->val);
        ListNode* tail = newhead;
        ListNode* cur = head->next;
        while (cur)
        {
            ListNode* newnode = new ListNode(cur->val);
            tail->next = newnode;
            tail = tail->next;
            cur = cur->next;

        }
        newhead = reverseList(newhead);
        cur = head;
        tail = newhead;
        while (cur)
        {
            if (cur->val != tail->val)
                return false;
            cur = cur->next;
            tail = tail->next;

        }


        return true;






    }
};
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};